69. x 的平方根

Similar Question

Solution Tips

方案一: 二分搜索

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

实现

  /**
   * @param {number} x
   * @return {number}
   */
  var mySqrt = function(x) {
    if(x<=1) return x
      let ans = 0
    let left=1,right=x
    let mid = 0
    while(left<=right){
      mid = (left+right) >>> 1
      if(mid**2 <= x){
        // 要增大
        left = mid + 1
        ans = mid
      }else{
        // 要变小
        right = mid -1
      }
    }
    return ans
  }

根据经验 right=x>>>1

模板实现

var mySqrt = function (x) {
    if (x == 0) return 0
    // 区间是1开始，要考虑特例0
    let left = 1, right = x >>> 1
    let mid = 0
    while (left < right) {
        mid = (left + right + 1) >>> 1
        if (mid ** 2 > x) {
            // 要变小，右，选择右中位数
            right = mid - 1
        } else {
            // 要增大
            left = mid
        }
    }
    return left || right
}